{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #图书整理 I"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #recursion #linked-list #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #递归 #链表 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: reverseBookList"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #图书整理 I"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>书店店员有一张链表形式的书单，每个节点代表一本书，节点中的值表示书的编号。为更方便整理书架，店员需要将书单倒过来排列，就可以从最后一本书开始整理，逐一将书放回到书架上。请倒序返回这个书单链表。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [3,6,4,1]\n",
    "\n",
    "<strong>输出：</strong>[1,4,6,3]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<p><code>0 &lt;= 链表长度 &lt;= 10000</code></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [cong-wei-dao-tou-da-yin-lian-biao-lcof](https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [cong-wei-dao-tou-da-yin-lian-biao-lcof](https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,6,4,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseBookList(self, head: Optional[ListNode]) -> List[int]:\n",
    "        #迭代法——双指针法\n",
    "        pre = None\n",
    "        cur = head\n",
    "\n",
    "        while cur :\n",
    "            tmp = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = tmp\n",
    "        res =  self.traverse(pre)\n",
    "        return res\n",
    "    \n",
    "    def traverse(self,head):\n",
    "        if not head:\n",
    "            return []\n",
    "        ret = []\n",
    "        cur = head\n",
    "        while cur:\n",
    "            ret.append(cur.val)\n",
    "            cur = cur.next\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseBookList(self, head: Optional[ListNode]) -> List[int]:\n",
    "        if head is None:\n",
    "            return []\n",
    "        # if head.next is None:\n",
    "        #     return head\n",
    "        prev = head\n",
    "        next_node = head.next\n",
    "        prev.next = None\n",
    "        while next_node is not None:\n",
    "            temp_save = next_node.next\n",
    "            next_node.next = prev\n",
    "            prev = next_node\n",
    "            next_node = temp_save\n",
    "        value_list = []\n",
    "        next_node = prev\n",
    "        while next_node is not None:\n",
    "            value_list.append(next_node.val)\n",
    "            next_node = next_node.next\n",
    "        return value_list\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseBookList(self, head: Optional[ListNode]) -> List[int]:\n",
    "        r = None\n",
    "        prv = None\n",
    "        cur = head\n",
    "        while cur is not None:\n",
    "            nxt = cur.next\n",
    "            cur.next = prv\n",
    "            prv = cur\n",
    "            cur = nxt\n",
    "\n",
    "        cur = prv\n",
    "        res = []\n",
    "        while cur is not None:\n",
    "            res.append(cur.val)\n",
    "            cur = cur.next\n",
    "\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "'''\n",
    "class Solution:\n",
    "    def reverseBookList(self, head: Optional[ListNode]) -> List[int]:       \n",
    "        if head:\n",
    "            ans = self.reverseBookList(head.next) + [ head.val ]\n",
    "        else:\n",
    "            ans = []\n",
    "        return ans\n",
    "'''\n",
    "class Solution:\n",
    "    def reverseBookList(self, head: Optional[ListNode]) -> List[int]:       \n",
    "        ans = []\n",
    "        while head!= None:\n",
    "            ans.append(head.val) \n",
    "            head = head.next\n",
    "        ans.reverse()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseBookList(self, head: Optional[ListNode]) -> List[int]:\n",
    "        if head is None:\n",
    "            return []\n",
    "        res = [head.val]\n",
    "        node = head\n",
    "        while node.next is not None:\n",
    "            res.append(node.next.val)\n",
    "            node = node.next\n",
    "\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseBookList(self, head: Optional[ListNode]) -> List[int]:\n",
    "        reverselist = []\n",
    "        while head:\n",
    "            reverselist.insert(0, head.val)\n",
    "            head = head.next\n",
    "        return reverselist\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseBookList(self, head: Optional[ListNode]) -> List[int]:\n",
    "        stack = []\n",
    "        result = []\n",
    "        while head:\n",
    "            stack.append(head.val)\n",
    "            head = head.next\n",
    "\n",
    "        for i in range(len(stack)):\n",
    "            n = stack.pop()\n",
    "            result.append(n)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseBookList(self, head: Optional[ListNode]) -> List[int]:\n",
    "        last=None\n",
    "        while head:\n",
    "            last = ListNode(val=head.val,next=last)\n",
    "            head = head.next\n",
    "        reverse_=[]\n",
    "        if last==None:\n",
    "            return []\n",
    "        while True:\n",
    "            reverse_.append(last.val)\n",
    "            next = last.next\n",
    "            if next:\n",
    "                last = next\n",
    "                continue\n",
    "            else:\n",
    "                break\n",
    "        return reverse_\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseBookList(self, head: Optional[ListNode]) -> List[int]:\n",
    "        if head == None:\n",
    "            return []\n",
    "        result = ListNode(head.val,None)\n",
    "        ptr = head\n",
    "        booklist = []\n",
    "        while ptr != None:\n",
    "            booklist.insert(0,ptr.val)\n",
    "            addnode = ListNode(ptr.val,result)\n",
    "            result = addnode\n",
    "            ptr = ptr.next\n",
    "        #return result\n",
    "        return booklist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseBookList(self, head: Optional[ListNode]) -> List[int]:\n",
    "        return self.reverseBookList(head.next) + [head.val] if head else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseBookList(self, head: Optional[ListNode]) -> List[int]:\n",
    "\n",
    "        if head == None:\n",
    "            return []\n",
    "\n",
    "        return  self.reverseBookList(head.next) + [head.val]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseBookList(self, head: Optional[ListNode]) -> List[int]:\n",
    "        return self.reverseBookList(head.next) + [head.val] if head else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseBookList(self, head: Optional[ListNode]) -> List[int]:\n",
    "        return self.reverseBookList(head.next)+[head.val] if head else []"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
